home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_10_08 / 1008020a < prev    next >
Text File  |  1992-02-05  |  5KB  |  152 lines
  1. ///////////////////////////////////////////////////////
  2. //  Listing 1 - QC.H: Header file for quadcodes
  3. //  by Kenneth Van Camp
  4. ///////////////////////////////////////////////////////
  5. typedef unsigned char BYTE;
  6. typedef long          COORD;
  7.  
  8. // The following should be defined on computers that 
  9. // store their most-significant byte first in integers:
  10. // #define MSB_FIRST
  11.  
  12. // Store (I,J) coordinates in long integers, so this is
  13. // the only limitation on the accuracy of storage:
  14. #define NBITS_COORD  sizeof(COORD) * 8
  15.  
  16. // Define the following to use static-length QuadCodes.
  17. // If not defined, dynamic allocation is used:
  18. #define STAT_QC
  19.  
  20. #ifdef STAT_QC
  21. # define NBYTE_QC   8    // # bytes to store a quadcode
  22. # define MAXQUITS   (min (NBITS_COORD, 4*NBYTE_QC))
  23. #else
  24. # define MAXQUITS   NBITS_COORD
  25. #endif
  26.  
  27. // class QuadCode: Store a single quadcode
  28. // (2 bits per quit).
  29. class QuadCode
  30. {
  31.   protected:
  32. #ifdef STAT_QC
  33.     BYTE qca[NBYTE_QC];   // storage area for quadcode
  34.     void FreeMem (void)   // free dynamic memory
  35.         { nquits=0; }
  36. #else
  37.     BYTE *qca;            // storage area for quadcode
  38.     void FreeMem (void);  // free dynamic memory
  39. #endif
  40.     void Init             // initializer from string
  41.         (const char *chqc);
  42.  
  43.   public:
  44.     int nquits;           // # of quits in qc
  45.     QuadCode (void)       // default constructor
  46.         { nquits = 0; }
  47.     QuadCode              // constructor from (I,J)
  48.         (COORD i, COORD j, int nq);
  49.     QuadCode              // constructor from string
  50.         (const char *chqc)
  51.         { Init (chqc); }
  52. #ifndef STAT_QC
  53.     ~QuadCode (void)      // destructor
  54.         { FreeMem(); }
  55. #endif
  56.     int GetQuit           // extract single quit
  57.         (int quit);
  58.     void SetQuit          // set single quit
  59.         (int quit, int val);
  60.     void ToIJ             // convert to (I,J)
  61.         (COORD &i, COORD &j, int &nq);
  62.     int Compare           // compare two quadcodes
  63.         (QuadCode &qc);
  64.     int Sibling           // is qc a sibling?
  65.         (const QuadCode *qc);
  66.     int Contains          // does one qc contain other?
  67.         (QuadCode &qc);
  68.     void MakeParent       // make qc into its parent
  69.         (void);
  70.  
  71.     QuadCode &operator= (QuadCode &qc);
  72.     int operator< (QuadCode &qc)
  73.       { return (this->Compare (qc) < 0); }
  74.     int operator> (QuadCode &qc)
  75.       { return (this->Compare (qc) > 0); }
  76.     int operator<= (QuadCode &qc)
  77.       { return (this->Compare (qc) <= 0); }
  78.     int operator>= (QuadCode &qc)
  79.       { return (this->Compare (qc) >= 0); }
  80.     int operator== (QuadCode &qc)
  81.       { return (this->Compare (qc) == 0); }
  82.     int operator!= (QuadCode &qc)
  83.       { return (this->Compare (qc) != 0); }
  84.  
  85.     friend ostream &operator<<
  86.       (ostream &stream, QuadCode &qc);
  87.     friend istream &operator>>
  88.       (istream &stream, QuadCode &qc);
  89. }; // class QuadCode
  90.  
  91. // class QCNode: A node in a linked list of quadcodes.
  92. class QCNode: public QuadCode
  93. {
  94.   private:
  95.     QCNode  *next;        // next node in linked list
  96.     // Friend classes for access to 'next'.
  97.     friend Region, RegionDisplay;
  98.     // Same for its "put to" operator.
  99.     friend ostream &operator<<
  100.       (ostream &stream, Region ®);
  101.  
  102.   public:
  103.     QCNode (void)         // default constructor
  104.         { next = NULL; }
  105.     QCNode                // constructor from (I,J)
  106.         (COORD i, COORD j, int nq):
  107.         QuadCode (i, j, nq)  // calls qc constr first
  108.         { next = NULL; }
  109. }; // class QCNode
  110.  
  111. // struct Point: One point on outline of region.
  112. struct Point
  113. {
  114.   COORD i, j;
  115. };
  116.  
  117. // struct PointListHeader: An array of points.
  118. struct PointListHeader
  119. {
  120.   int length;             // # of points in array
  121.   COORD ndiv;             // # (I,J) divisions in grid
  122.   struct Point *pointptr; // array of points
  123. };
  124.  
  125. // class Region: A linked list of QuadCodes
  126. class Region
  127. {
  128.   protected:
  129.     QCNode *first_qcnode; // start of linked list
  130.     COORD ndiv;           // # (I,J) divisions in grid
  131.     void ScanOutAET       // create qc's along one row
  132.         (COORD i_to_scan, int &nqc_compress, int nquits);
  133.     void AddRow           // add row of qc's
  134.         (COORD i, COORD j1, COORD j2, int nquits);
  135.     void AddQC            // add a single qc
  136.         (COORD i, COORD j, int nquits);
  137.     int MaxQuits (void);  // find max #quits in a qc
  138.  
  139.   public:
  140.     Region (void)         // default constructor
  141.       { first_qcnode = NULL; ndiv = 0; }
  142.     Region                // constructor from outline
  143.         (PointListHeader &vertext_list);
  144.     ~Region (void);       // destructor
  145.     int Compress (void);  // region compressor
  146.     int InRegion          // is qc in region?
  147.         (QuadCode &qc);
  148.     int NumQC (void);     // count quadcodes in region
  149.     friend ostream &operator<<
  150.       (ostream &stream, Region ®);
  151. }; // class Region
  152.